package com.lee.algorithm.tree;

import com.lee.algorithm.tree.struct.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/***
 * @description: 打印二叉树
 *      任何递归都可以改成非递归实现
 *      前、中、后序，都是站在根节点的角度
 * @author 博客园 @ 青石路
 * @date: 2021/12/4 15:36
 */
public class PrintBinaryTree {

    /**
     * 递归 - 先序打印
     *
     * @author 博客园 @ 青石路
     * @param node
     */
    public static void preOrderRecur(TreeNode node) {
        if(node == null) {
            return;
        }
        System.out.print(node.value + " ");
        preOrderRecur(node.left);
        preOrderRecur(node.right);
    }

    /**
     * 递归 - 中序打印
     *
     * @author 博客园 @ 青石路
     * @param node
     */
    public static void inOrderRecur(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrderRecur(node.left);
        System.out.print(node.value + " ");
        inOrderRecur(node.right);
    }

    /**
     * 递归 - 后续打印
     *
     * @author 博客园 @ 青石路
     * @param node
     */
    public static void posOrderRecur(TreeNode node) {
        if (node == null) {
            return;
        }
        posOrderRecur(node.left);
        posOrderRecur(node.right);
        System.out.print(node.value + " ");
    }

    /**
     * 非递归 - 先序打印
     *      压栈的过程我们自己控制，不交由JVM
     *      栈：先进后出
     *
     *      1、弹出cur，并打印cur
     *      2、压入cur的right、left
     *      3、循环 1、2 处理栈，直到栈为空
     *
     * @author 博客园 @ 青石路
     * @param node
     */
    public static void preOrderUnRecur(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(node);
        TreeNode cur;
        while (!stack.isEmpty()) {
            cur = stack.pop();
            System.out.print(cur.value + " ");
            // 右先入栈，再左入栈；栈是先进后出
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

    /**
     * 非递归 - 中序打印
     *      一个节点作为一个子树来考虑，从子树扩大到整棵树
     *      1、cur入栈，处理 cur 的左子树
     *      2、重复步骤 1，直到左子树都入栈
     *      3、从栈中弹出 cur，打印 cur，并将 cur 的右子树入栈
     *      4、重复 1，2，3
     *
     *      所有的树都可以被左边界分解掉（同样可以被右边界分解掉）
     *          子树的根节点可以划分左边界中
     *          叶子节点的左边界就是自己
     *
     *      结合代码理解
     * @author 博客园 @ 青石路
     * @param node
     */
    public static void inOrderUnRecur(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = node;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {      // 左边的持续入栈
                stack.push(cur);
                cur = cur.left;
            } else {                // 弹出 cur 后，跳到右边，继续处理左边界
                cur = stack.pop();
                System.out.print(cur.value + " ");
                cur = cur.right;
            }
        }
    }

    /**
     * 非递归 - 后续打印
     *      1、从s1弹出cur，将cur压入栈 s2
     *      2、将cur的left、right压入s1
     *      3、重复 1、2，处理s1，直到s1为空
     *      4、弹出 s2 中的元素并打印
     *
     *      头右左的方式入s2，s2出栈的时候则是 左右头
     *
     * @author 博客园 @ 青石路
     * @param node
     */
    public static void posOrderUnRecur(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.add(node);
        TreeNode cur;
        while (!s1.isEmpty()) {
            cur = s1.pop();
            s2.push(cur);
            if (cur.left != null) {
                s1.push(cur.left);
            }
            if (cur.right != null) {
                s1.push(cur.right);
            }
        }
        while(!s2.isEmpty()) {
            System.out.print(s2.pop().value + " ");
        }
    }

    // 深度优先遍历 就是 先序遍历二叉树（递归或栈可以解决）
    /**
     * 从上至下层次遍历（广度优先遍历），用队列
     *
     * @author 博客园 @ 青石路
     * @param node
     */
    public static void widthOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.value + " ");
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }

    /**
     * 从下至上层次遍历
     *      队列用于宽度遍历
     *      栈用于倒置，实现从下至上
     *
     * @author 博客园 @ 青石路
     * @param node
     */
    public static void widthOrderReverse(TreeNode node) {
        if (node == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            stack.add(cur);

            // 先处理右子树，相当于右先入栈；栈是先进后出
            if (cur.right != null) {
                queue.add(cur.right);
            }
            if (cur.left != null) {
                queue.add(cur.left);
            }
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop().value + " ");
        }
    }

    /**
     * 求二叉树的最大宽度 - 采用哈希表
     *      宽度遍历，标记节点所在的层次，同时统计当前层的节点个数
     *
     * @author 博客园 @ 青石路
     * @param root
     * @return
     */
    public static int getMaxWidth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        HashMap<TreeNode, Integer> levelMap = new HashMap<>(); // 记录节点所在的层数
        levelMap.put(root, 1);      // 根节点在第一层
        int curLevel = 1;           // 当前层
        int curLevelNodes = 0;      // 当前层的节点数
        int max = 0;

        // 队列辅助实现宽度遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int curNodeLevel = levelMap.get(cur);       // 当前节点所在的层数

            // 宽度遍历是一层一层进行的，所以当前节点要么属于当前层，要么属于下一层
            if (curNodeLevel == curLevel) {
                curLevelNodes ++;
            } else {
                // 一旦当前节点不属于当前层，那肯定属于下一层
                // 所以上一层已经结算完，从当前节点开始，统计下一层
                max = Math.max(max, curLevelNodes);
                curLevel ++;
                curLevelNodes = 1;
            }

            if (cur.left != null) {
                levelMap.put(cur.left, curNodeLevel + 1);
                queue.add(cur.left);
            }
            if (cur.right != null) {
                levelMap.put(cur.right, curNodeLevel + 1);
                queue.add(cur.right);
            }
        }
        return max;
    }

    /**
     * 求二叉树的最大宽度 - 不用哈希表
     *
     * @author 博客园 @ 青石路
     * @param node
     * @return
     */
    public static int getMaxWidthPlus(TreeNode node) {
        if (node == null) {
            return 0;
        }

        TreeNode curEnd = node;         // 记录当前层的最后一个节点
        TreeNode nextEnd = null;        // 记录下一层的最后一个节点
        int curNodes = 1;               // 当前层的节点数
        int max = 0;

        // 宽度遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {

            // 宽度遍历的同时移动 nextEnd
            TreeNode cur = queue.poll();
            if (cur.left != null) {
                nextEnd = cur.left;
                queue.add(cur.left);
            }
            if (cur.right != null) {
                nextEnd = cur.right;
                queue.add(cur.right);
            }

            if (cur == curEnd) {        // 当前层结算完，开始下一层
                max = Math.max(max, curNodes);
                curEnd = nextEnd;
                curNodes = 1;
            } else {                    // 还在处理当前层
                curNodes++;
            }
        }

        return max;
    }

    public static void main(String[] args) {

        TreeNode<String> head = TreeUtil.initBinaryTree();
        preOrderRecur(head);

        // widthOrderReverse(head);

        /*widthOrder(head);
        int maxWidth = getMaxWidthPlus(head);
        System.out.println("最大宽度：" + maxWidth);*/
    }
}
